package tools;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import datatypes.Edge;
import datatypes.OrientedLine2D;
import datatypes.Vertex;
import datatypes.VertexXCoordinateComparator;

/**
 * 
 * @author PSeiferth, nils
 * 
 */
public class ConvexHullCreator {
    
    /**
     * This method returns a ordered List of vertices which represents the convex hull of the 
     * given vertex set . The convex hull is computed using the GrahamsScan algorithm which
     * has a running time of O(n log n) where n is the number of vertices.
     * Note that the first vertex of the convex hull occurs at the end of the returned List too.
     * 
     * @param vertices 
     *          the point set
     * @return 
     *          a ordered List<Vertex> which represents the convex hull 
     * 
     */
    public static List<Vertex> doGrahamsScan(List<Vertex> vertices) {

        List<Vertex> convexHull = new ArrayList<Vertex>();
        if (vertices.size() == 0) {
			return convexHull;
		}
        
        
        // sort point set according to x-coordinate from left to right
        Collections.sort(vertices, new VertexXCoordinateComparator());

        // the convex hull contains always the leftmost point
        convexHull.add(vertices.get(0));
        convexHull.add(vertices.get(1));

        // Upper convex hull
        for (int i = 2; i < vertices.size(); i++) {
            convexHull.add(vertices.get(i));
            OrientedLine2D line = new OrientedLine2D(convexHull.get(convexHull.size() - 3),
                    convexHull.get(convexHull.size() - 2));

            // test if the the new point p_i+1 lies left of the oriented line between p_i-1 and p_i. If the
            // point lies left
            // of this line, remove p_i and do the same test again until it is right of this line. Else do
            // nothing.
            while (line.isLeftOf(convexHull.get(convexHull.size() - 1)) > 0) {
                convexHull.remove(convexHull.size() - 2);
                
                //stop if there are just 2 points left in the convex hull. 
                //These 2 have to be on the convex hull
                if (convexHull.size() <= 2) break;
                
                line = new OrientedLine2D(convexHull.get(convexHull.size() - 3), convexHull.get(convexHull
                        .size() - 2));
            }

        }

        // Lower convex hull
        for (int i = vertices.size() - 2; i >= 0; i--) {
            convexHull.add(vertices.get(i));
            OrientedLine2D line = new OrientedLine2D(convexHull.get(convexHull.size() - 3),
                    convexHull.get(convexHull.size() - 2));

            // test if the the new point p_i+1 lies left of the oriented line between p_i-1 and p_i. If the
            // point lies left
            // of this line, remove p_i and do the same test again until it is right of this line. Else do
            // nothing.
            while (line.isLeftOf(convexHull.get(convexHull.size() - 1)) > 0) {
                convexHull.remove(convexHull.size() - 2);
                
                //stop if there are just 2 points left in the convex hull. 
                //These 2 have to be on the convex hull
                if (convexHull.size() <= 2) break;
                
                line = new OrientedLine2D(convexHull.get(convexHull.size() - 3), convexHull.get(convexHull
                        .size() - 2));
            }
        }

        return convexHull;
    }

    
    /**
     * This method returns a ordered List of vertices which represents the convex hull of the 
     * given vertex set . The convex hull is computed using the Jarvis's March algorithm which
     * has a running time of O(n*h) where n is the number of vertices and h is the number of 
     * vertices on the convex hull.
     * Note that the first vertex of the convex hull occurs at the end of the returned List too.
     * 
     * @param vertices
     *          the point set
     * @return 
     *          a ordered List<Vertex> which represents the convex hull 
     * 
     */
    
    @SuppressWarnings("null")
	public static List<Vertex> doJarvisMarch(List<Vertex> vertices) {
        List<Vertex> convexHull = new ArrayList<Vertex>();
        if (vertices.size() == 0) {
			return convexHull;
		}

        Vertex leftmost = vertices.get(0);
        for (Vertex point : vertices) {
            if (point.getX() < leftmost.getX()) {
                leftmost = point;
            }
        }
        OrientedLine2D line = new OrientedLine2D(new Vertex(leftmost.getX(), leftmost.getY() - 1), leftmost);
        OrientedLine2D newLine, minimizedLine = null;
        double minimizedAngle = 100000000000.0;
        Vertex active = leftmost;
        convexHull.add(active);
        do {
            for (Vertex point : vertices) {
                if (point == active || (point.getX() == active.getX() && point.getY() == active.getY())) {
                    continue;
                }
                newLine = line.rotateTo(point);
                double newAngle = line.angleWith(newLine);
                if (minimizedLine == null || newAngle < minimizedAngle) {
                    minimizedLine = newLine;
                    minimizedAngle = newAngle;
                    // System.out.println("minimized at " + vertex);
                }
            }
            active = minimizedLine.getEndPoint();
            line = minimizedLine;
            minimizedLine = null;
            // System.out.println("new active at " + active);
            convexHull.add(active);
        } while (active != leftmost);
        return convexHull;
    }

    /**
     * Takes a bunch of points as returned by the hull generator function and locates the appropriate hull
     * edges from an in-passed list of all possible edges
     * 
     * @param points
     *            The set of points
     * @return The list of only the hull edges
     */
    public static List<Edge> getHullEdges(List<Vertex> points) {

        ArrayList<Edge> edges = new ArrayList<Edge>();

        for (int i = 0; i < points.size() - 1; i++) {

            Vertex start = points.get(i);
            Vertex end = points.get(i + 1);

            edges.add(new Edge(start, end));
        }
        return edges;
    }

    
	/**
	 * Takes a bunch of points as returned by the hull generator function and
	 * locates the appropriate hull edges from an in-passed list of all possible
	 * edges
	 * @param points The set of points
	 * @return The list of only the hull edges
	 */
    
	public static List<Edge> getHullEdges(List<Vertex> points, List<Edge> candEdges) {

		ArrayList<Edge> edges = new ArrayList<Edge>();
		
		for (int i = 0;i<points.size()-1;i++)  {
			
			Vertex start = points.get(i);
			Vertex end = points.get(i+1);
			
			for (Edge e: candEdges) {
				if (e.connectsCoordinates(start, end))
					edges.add(e);
			}
		}
		return edges;
	}
    
}
